from functools import cache

# 递归+记忆化搜索
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        print(n, m)

        # 对于当前i 有三种操作
        @cache
        def dfs(i, j):

            if j >= m:
                # 删除
                return n - i
            if i >= n:
                # 插入
                return abs(m - j)
            # 相等递归到下一层
            if word1[i] == word2[j]:
                return dfs(i + 1, j + 1)
            # 替换 插入 删除
            else:
                return min(dfs(i + 1, j + 1) + 1, dfs(i, j + 1) + 1, dfs(i + 1, j) + 1)

        return dfs(0, 0)

# dp 动态规划
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        print(n, m)
        # 对于当前i 有三种操作
        # @cache
        # def dfs(i,j):

        #     if j>=m:
        #         # 删除
        #         return n-i
        #     # 最后一层
        #     if i>=n:
        #         # 插入
        #         return abs(m-j)

        #     if word1[i]==word2[j]:
        #         return dfs(i+1,j+1)
        #     # 替换 插入 删除
        #     else:
        #         return min(dfs(i+1,j+1)+1,dfs(i,j+1)+1,dfs(i+1,j)+1)
        # return dfs(0,0)
        # 递归的递是把当前状态看作起始状态，当前操作是考虑怎么递归到下一个状态
        # 递归的归是把当前操作看作最终状态，当前操作是考虑怎么递归到前一个状态
        # dp是把当前状态看作最终状态，它的状态由前一个i-1,j-1相关得来
        # 递归的归 == dp操作
        # 把递归的递改写dp，i,j不变， + - 操作 变为 - + 操作，其他看意思改写
        # dp[i][j]表示将word1的前i个字符转换为word2的前j字符需要的最少操作次数
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        # 递归中的边界条件，相当于 dp中的初始化条件
        # 当word1 为空,将空字符转换为word2的前j个字符需要j次插入操作
        for j in range(m + 1):
            dp[0][j] = j
        # 当word2为空，将word1的前i个字符转换为空字符需要i次删除操作
        for i in range(n + 1):
            dp[i][0] = i
        for i in range(1, n + 1):
            for j in range(1, m + 1):

                if word1[i - 1] == word2[j - 1]:
                    # 如果当前元素相等，则不需要额外操作，继承前一个状态的结果
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
        return dp[n][m]